//<p>给你一个整数 <code>n</code> ，按字典序返回范围 <code>[1, n]</code> 内所有整数。</p>
//
//<p>你必须设计一个时间复杂度为 <code>O(n)</code> 且使用 <code>O(1)</code> 额外空间的算法。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 13
//<strong>输出：</strong>[1,10,11,12,13,2,3,4,5,6,7,8,9]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 2
//<strong>输出：</strong>[1,2]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li> 
//</ul>
//
//<div><li>👍 490</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        dfs(0, n, ans);
        return ans;
    }

    // 迭代写法
    // vector<int> lexicalOrder(int n) {
    //     vector<int> ans;
    //     // i用来计数
    //     for (int i = 0, j = 1; i < n; i++) {
    //         ans.push_back(j);
    //         if (j * 10 <= n) {
    //             j *= 10;
    //         } else {
    //             while (j % 10 == 9 || j + 1 > n) j /= 10;
    //             j++;
    //         }
    //     }
    //     return ans;
    // }

private:
    void dfs(int cur, int n, vector<int>& ans) {
        if (cur > n) return;
        if (cur > 0) ans.push_back(cur);
        for (int i = cur == 0 ? 1 : 0; i < 10; i++) {
            dfs(cur * 10 + i, n, ans);
        }
    }
};

//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    auto ans = s.lexicalOrder(13);
    cout << ans.size() << endl;
}
